In the computer art, an interrupt, as is well known, is an asynchronous signal to the processor that requires the attention of the processor. If multiple interrupts are received simultaneously or if an interrupt is received while the processor is handling another interrupt, it is necessary to employ some type of interrupt handling algorithm to handle the competing interrupts.
In certain computer systems, interrupts are stored in a central control register upon receipt and handled according to their priority levels. In the central control register, the interrupts are sorted based on the interrupts' vector numbers. The processor then accesses the central control register and handles the interrupts starting with the interrupt having the highest vector number.
While an interrupt is being handled, it is possible that another arriving interrupt may have a higher priority and may need immediate attention by the processor. To handle these situations, interrupts are mapped into priority levels, and an interrupt that is mapped into a higher priority level is handled ahead of an interrupt that is mapped into a lower priority level. For example, interrupts with vector numbers in the range from 0–15 may be mapped into priority level 1. Interrupts with vector numbers in the range from 48–63 may be mapped into priority level 4, and interrupts with vector numbers in the range from 64–79 may be mapped into priority level 5. A task priority register (TPR) keeps track of the priority level associated with the interrupt currently being handled by the processor.
If the processor is servicing an interrupt with a vector number that maps into a particular TPR value, the arrival of another interrupt would be ignored by the processor unless the priority level associated with the newly arriving interrupt is higher than the priority level represented in the TPR. For example, if the processor is currently servicing an interrupt having an interrupt vector of 47 (which maps into priority level 4), the current TPR value would be 4. Any subsequently arriving interrupt, such as an interrupt having a vector value of 11, would be ignored since such subsequently arriving interrupt maps into priority level 1, i.e., a lower priority level than that represents by the current TPR value of 4. On the other hand, a subsequently arriving interrupt having a vector value of 77 would be able to jump ahead of the line and get the processor's attention since an interrupt vector value of 77 maps into priority level 5, i.e., a priority level higher than that represented by the current TPR value of 4.
As mentioned, the interrupts are stored in a central control register while they wait to be handled by the processor. In the IPF® (Itanium Processor Family) family of processors, which is available from the Intel Corporation of Santa Clara, Calif., an IVR register is employed to store the received interrupts. As each interrupt is received, it is sorted and stored in the IVR register. The processor then process the received interrupts in the IVR register in accordance with some interrupt handling algorithm, starting with the interrupt having the highest vector number.
FIG. 1 shows a prior art implementation whereby an algorithm has been implemented to manage pending interrupts in a computer system that employs the IPF architecture. Generally speaking, as an interrupt is taken from the IVR register to be handled, the TPR level is masked to the priority level associated with the interrupt that is about to be handled. For example, if the TPR level has been 0, e.g., the processor has not been servicing any interrupt, the TPR level will be set to 5 if an interrupt having an interrupt vector number of 77 is taken from the IVR to be handled next. This is because, as mentioned, the vector value of 77 maps into priority level 5.
The processor then handles the interrupt whose interrupt vector number is 77. Since the TPR level is set to 5, the processor will ignore all incoming interrupts whose priority level is 5 or lower. Assuming no higher level interrupt is received, the processor will finish servicing the interrupt that has the vector number of 77, and returns to the previous TPR level (i.e., zero in the present example). At this point, with the TPR lowered again, the processor can access all interrupts irrespective of their vector numbers. The processor then accesses the IVR register to ascertain the highest priority interrupt in the IVR to handle next. If the interrupt that has the highest vector number in the IVR is now 8 (which maps into priority level 1 per the present example), the fact that the TPR has been restored to its previous value (i.e., zero in this example) allows the processor to take note of this interrupt. The process then reads the interrupt with the highest vector number in the IVR, handles that interrupt, and continues in this manner until all pending interrupts are handled.
The sequence described above is illustrated in FIG. 1. Referring now to FIG. 1, in step 102, the interrupt in the IVR that has the highest vector number is ascertained. This is the interrupt to be handled next. In step 104, the TPR level is set to the priority level associated with the vector number of the interrupt about to be handled. This setting of the TPR level, as mentioned, enables a subsequently received interrupt having a higher priority level than the priority level of the interrupt about to be handled to immediately get the attention of the processor even while the processor is busy handling interrupts. Any subsequently received interrupt having the same priority level or a lower priority level than the priority level of the interrupt being handled will be ignored by the processor while it is servicing the current interrupt. On the other hand, any subsequently received interrupt having a higher priority level than the priority level of the interrupt being handled will be able to get the attention of the processor
In step 106, the interrupt mechanism is enabled. The enabling of the interrupt mechanism permits a higher priority interrupt that may be subsequently received to immediately get the attention of the processor. In step 108, the current interrupt is handled. After the interrupt is handled, the interrupt mechanism is disabled in step 110. In step 112, the processor signals that it has finished servicing the interrupt it has recently taken from the IVR by writing a value “0” (i.e., zero) into the control register EOI. Thereafter, the TPR value is reset to the original TPR value (e.g., zero in the current example) in step 114. In step 116, the next interrupt is read from the IVR. If the next interrupt is equal to the flag “spurious” (which is an arbitrary value selected to signal that there are no more pending interrupts in the IVR), the IVR is empty. In this case, the algorithm ends at step 120. On the other hand, if the next interrupt read from the IVR is not equal to the flag “spurious,” the method returns to step 104 to reset the TPR value to the priority level associated with the vector number of the interrupt in the IVR that is to be serviced next (i.e., the interrupt that currently has the highest vector number in the IVR).
It has been found, however, that the prior art approach for handling pending interrupts has certain disadvantages. In particular, the prior art algorithm may result, in certain situations, an interrupt starvation condition for some interrupts. To facilitate discussion, consider the example of FIG. 2, which covers four time periods: T0, T1, T2, and T3. At time T0, the IVR 202 shows three interrupts, whose vector numbers are 77, 75, and 62 respectively. These may be sorted by their vector numbers in the IVR.
At time T0, the interrupt having the vector number of 77 is the one with the highest vector number in the IVR and is thus read and handled first (step 102 of FIG. 1). Assuming that prior to the handling of this interrupt, the processor is coming from a non-masked situation (i.e., it has not been handling any interrupt). Thus, the current TPR level is zero (step 102).
The TPR level is then set to 5 since the vector number of 77 maps into priority level 5 (step 104). The interrupt is then enabled (step 106). The processor then handles the interrupt (step 108). The interrupt is then disabled (step 110). Thereafter, the value “0” is written into the EOI control register (step 112). The TPR is restored to its previous value of “0” (step 114).
At time T1, the process then accesses the IVR to read the next interrupt vector (step 116). As can be seen, an interrupt vector number 76 has been received since time T0, and it is now sorted to be at the top of the pending interrupts list in the IVR. Since there are interrupts pending in the IVR, the new interrupt vector is not spurious. Accordingly, the method begins to service the next interrupt that it just read in (step 118 back to step 104).
The TPR level is then set to 5 since the vector number of 76 maps into priority level 5 (step 104). The interrupt is then enabled (step 106). The processor then handles the interrupt (step 108). The interrupt is then disabled (step 110). Thereafter, the value “0” is written into the EOI control register (step 112). The TPR is restored to its previous value of “0” (step 114).
At time T2, the process then accesses the IVR to read the next interrupt vector (step 116). As can be seen, an interrupt vector number 77 has been received again since time T1, and it is now sorted to be at the top of the pending interrupts list in the IVR. Since there are interrupts pending in the IVR, the new interrupt vector is not spurious. Accordingly, the method begins to service the next interrupt that it just read in (step 118 back to step 104).
The TPR level is then set to 5 since the vector number of 77 maps into priority level 5 (step 104). The interrupt is then enabled (step 106). The processor then handles the interrupt (step 108). The interrupt is then disabled (step 110). Thereafter, the value “0” is written into the EOI control register (step 112). The TPR is restored to its previous value of “0” (step 114).
At time T3, the process then accesses the IVR to read the next interrupt vector (step 116). As can be seen, an interrupt vector number 76 has been received again since time T1, and it is now sorted to be at the top of the pending interrupts list in the IVR. Since there are interrupts pending in the IVR, the new interrupt vector is not spurious. Accordingly, the method begins to service the next interrupt that it just read in (step 118 back to step 104).
The TPR level is then set to 5 since the vector number of 76 maps into priority level 5 (step 104). The interrupt is then enabled (step 106). The processor then handles the interrupt (step 108). The interrupt is then disabled (step 110). Thereafter, the value “0” is written into the EOI control register (step 112). The TPR is restored to its previous value of “0” (step 114).
Note also that even though interrupt vector 62 does not get handled in the current sequence, this is the correct result since interrupt vector 62 maps into priority level 4, and thus interrupt vector 62 cannot be serviced before interrupt vectors 77, 76, or 75 (which are all mapped to priority level 5) irrespective of how long it waits in the IVR.
However, interrupt vector 75 also does not get handled even though it has the same priority level as interrupt vector 77 and interrupt vector 76, both of which have been able to jump ahead of interrupt vector 75. In other words, interrupt vector 75 is unfairly starved even though it is at the same priority level as interrupt vector 77 and interrupt vector 76 and thus should not be trumped by interrupt vector 77 and interrupt vector 76.